Anchoring millions of distinct reads on the human genome within seconds.
With the advent of next-generation DNA sequencing machines, there is an increasing need for the development of computational tools that can anchor accurately and expediently the millions of generated short DNA sequences (or reads) onto the genomes of target organisms. In this work, we describe ‘Q-Pick’, a new and efficient method for solving this problem. Q-Pick allows the rapid identification and anchoring of such reads with possible wildcards in large genomic databases, while guaranteeing completeness of results and efficiency of operation. Q-Pick requires very spartan memory and computational resources, and is trivially amenable to SIMD implementation; it can also be easily extended to handle longer reads, e.g. 75-mers or longer. Our experiments indicate that Q-Pick can anchor millions of distinct short reads against both strands of a mammalian genome in seconds, using a single-core computer processor. 1.
Mining Time Series Data.
The last decade has witnessed a tremendous growths of interests in applications that deal with querying and mining of time series data. Numerous representation methods for dimensionality reduction and similarity measures geared towards time series have been introduced. Each individual work introducing a particular method has made specific claims and, aside from the occasional theoretical justifications, provided quantitative experimental observations. However, for the most part, the comparative aspects of these experiments were too narrowly focused on demonstrating the benefits of the proposed methods over some of the previously introduced ones. In order to provide a comprehensive validation, we conducted an extensive set of time series experiments re-implementing 8 different representation methods and 9 similarity measures and their variants, and testing their effectiveness on 38 time series data sets from a wide variety of application domains. In this paper, we give an overview of these different techniques and present our comparative experimental findings regarding their effectiveness. Our experiments have provided both a unified validation of some of the existing achievements, and in some cases, suggested that certain claims in the literature may be unduly optimistic. 1.
Net%2DFli On%2Dthe%2Dfly Compression
The ever-increasing number of intrusions in public and commercial networks has created the need for high-speed archival solutions that continuously store streaming network data to enable forensic analysis and auditing. However, “turning back the clock ” for post-attack analyses is not a trivial task. The first major challenge is that the solution has to sustain data archiving under extremely high-speed insertion rates. Moreover, the archives created need to be stored in a format that is compressed but still amenable to indexing. The above requirements make general-purpose databases unsuitable for this task, and, thus, dedicated solutions are required. In this paper, we describe a prototype solution that satisfies all requirements for high-speed archival storage, indexing and data querying on network flow information. The superior performance of our approach is attributed to the on-the-fly compression and indexing scheme, which is based on compressed bitmap principles. Typical commercial solutions can currently process 20,000-60,000 flows per second. An evaluation of our prototype implementation on current commodity hardware using real-world traffic traces shows its ability to sustain insertion rates ranging from 500,000 to more than 1 million records per second. The system offers interactive query response times that enable administrators to perform complex analysis tasks on-the-fly. Our technique is directly amenable to parallel execution, allowing its application in domains that are challenged by large volumes of historical measurement data, such as network auditing, traffic behavior analysis and large-scale data visualization in service provider networks. 1.
Optimal distance bounds for fast search on compressed time%2Dseries query logs.

Rights protection of trajectory datasets with nearest%2Dneighbor preservation.

On K%2DMeans Cluster Preservation Using Quantization Schemes.
This work examines under what conditions compression methodologies can retain the outcome of clustering operations. We focus on the popular k-Means clustering algorithm and we demonstrate how a properly constructed compression scheme based on post-clustering quantization is capable of maintaining the global cluster structure. Our analytical derivations indicate that a 1-bit moment preserving quantizer per cluster is sufficient to retain the original data clusters. Merits of the proposed compression technique include: a) reduced storage requirements with clustering guarantees, b) data privacy on the original values, and c) shape preservation for data visualization purposes. We evaluate quantization scheme on various high-dimensional datasets, including 1-dimensional and 2-dimensional timeseries (shape datasets) and demonstrate the cluster preservation property. We also compare with previously proposed simplification techniques in the time-series area and show significant improvements both on the clustering and shape preservation of the compressed datasets. 1
Optimal Distance Bounds on Time%2DSeries Data.
Most data mining operations include an integral search component at their core. For example, the performance of similarity search or classification based on Nearest Neighbors is largely dependent on the underlying compression and distance estimation techniques. As data repositories grow larger, there is an explicit need not only for storing the data in a compressed form, but also for facilitating mining operations directly on the compressed data. Naturally, the quality or tightness of the estimated distances on the compressed objects directly affects the search performance. We motivate our work within the setting of search engine weblog repositories, where keyword demand trends over time are represented and stored as compressed timeseries data. Search and analysis over such sequence data has important applications for the search engines, including discovery of important news events, keyword recommendation and efficient keyword-to-advertisement mapping. We present new mechanisms for very fast search operations over the compressed time-series data, with specific focus on weblog data. An important contribution of this work is the derivation of optimally tight bounds on the Euclidean distance estimation between compressed sequences. Since our methodology is applicable to sequential data in general, the proposed technique is of independent interest. Additionally, our distance estimation strategy is not tied to a specific compression methodology, but can be applied on top of any orthonormal based compression technique (Fourier, Wavelet, PCA, etc). The experimental results indicate that the new optimal bounds lead to a significant improvement in the pruning power of search compared to previous state-of-the-art, in many cases eliminating more than 80 % of the candidate search sequences. 1
Indexing and Similarity Search.

Finding the K highest%2Dranked answers in a distributed network.

Information discovery across multiple streams.
In this paper we address the issue of continuous keyword queries on multiple textual streams and explore techniques for extracting useful information from them. The paper represents, to our best knowledge, the first approach that performs keyword search on a multiplicity of textual streams. The scenario that we consider is quite intuitive; let&#039;s assume that a research or financial analyst is searching for information on a topic, continuously polling data from multiple (and possibly heterogeneous) text streams, such as RSS feeds, blogs, etc. The topic of interest can be
Embedding and Retrieving Private Metadata in Electrocardiograms.

Online pairing of VoIP conversations.

Supporting exact indexing of arbitrarily rotated shapes and periodic time series under Euclidean and warping distance measures.

Ownership protection of shape datasets with geodesic distance preservation.

Rights Protection of Trajectory Datasets.

Trajectories%2C Discovering Similar.


Correlating burst events on streaming stock market data.


Computing Correlation Anomaly Scores Using Stochastic Nearest Neighbors.
This paper addresses the task of change analysis of correlated multi-sensor systems. The goal of change analysis is to compute the anomaly score of each sensor when we know that the system has some potential difference from a reference state. Examples include validating the proper performance of various car sensors in the automobile industry. We solve this problem based on a neighborhood preservation principle — If the system is working normally, the neighborhood graph of each sensor is almost invariant against the fluctuations of experimental conditions. Here a neighborhood graph is defined based on the correlation between sensor signals. With the notion of stochastic neighborhood, our method is capable of robustly computing the anomaly score of each sensor under conditions that are hard to be detected by other naive methods. 1
Visual Exploration of Genomic Data.
The widespread acceptance and uptake of Grid technology can only be achieved if it can be ensured that the security mechanisms needed to support Grid based collaborations are at least as strong as local security mechanisms. The predominant way in which security is currently addressed in the Grid community is through Public Key Infrastructures (PKI) to support authentication. Whilst PKIs address user identity issues, authentication does not provide fine grained control over what users are allowed to do on remote resources (authorisation). The Grid community have put forward numerous software proposals for authorisation infrastructures such as AKENTI [1], CAS [2], CARDEA [3], GSI [4], PERMIS [5,6,7] and VOMS [8,9]. It is clear that for the foreseeable future a collection of solutions will be the norm. To address this, the Global Grid Forum (GGF) have proposed a generic SAML based authorisation API which in principle should allow for fine grained control for authorised access to any Grid service. Experiences in applying and stress testing this API from a variety of different application domains are essential to give insight into the practical aspects of large scale usage of authorisation infrastructures. This paper presents experiences from the DTI funded BRIDGES project [10] and the JISC funded DyVOSE project [11] in using this API with Globus version 3.3 [12] and the PERMIS authorisation infrastructure. 
A System for Keyword Search on Textual Streams.

Domain%2DDriven%2C Actionable Knowledge Discovery.

Continuous keyword search on multiple text streams.
In this paper we address the issue of continuous keyword queries on multiple textual streams and explore techniques for extracting useful information from them. The paper represents, to our best knowledge, the first approach that performs keyword search on a multiplicity of textual streams. The scenario that we consider is quite intuitive; let&#039;s assume that a research or financial analyst is searching for information on a topic, continuously polling data from multiple (and possibly heterogeneous) text streams, such as RSS feeds, blogs, etc. The topic of interest can be
Resource Adaptive Periodicity Estimation of Streaming Data.

Finding %22Who Is Talking to Whom%22 in VoIP Networks via Progressive Stream Clustering.

Global distance%2Dbased segmentation of trajectories.
This work introduces distance-based criteria for segmentation of object trajectories. Segmentation leads to simplification of the original objects into smaller, less complex primitives that are better suited for storage and retrieval purposes. Previous work on trajectory segmentation attacked the problem locally, segmenting separately each trajectory of the database. Therefore, they did not directly optimize the inter-object separability, which is necessary for mining operations such as searching, clustering, and classification on large databases. In this paper we analyze the trajectory segmentation problem from a global perspective, utilizing data aware distance-based optimization techniques, which optimize pairwise distance estimates hence leading to more efficient object pruning. We first derive exact solutions of the distance-based formulation. Due to the intractable complexity of the exact solution, we present an approximate, greedy solution that exploits forward searching of locally optimal solutions. Since the greedy solution also imposes a prohibitive computational cost, we also put forward more lightweight variance-based segmentation techniques, which intelligently “relax ” the pairwise distance only in the areas that affect the least the mining operations.
Efficient Online State Tracking Using Sensor Networks.
Sensor networks are being deployed for tracking events of interest in many environmental or monitoring applications. Because of their distributed nature of operation, a challenging issue is how to accurately identify the aggregate state of the phenomenon that is being observed. This work presents an online mechanism for efficiently determining the overall network status, employing distributed operations that minimize the communication costs. Experiments on real data, suggest that the proposed metholology can be a viable solution for real world systems. 1.
RIVA Indexing and Visualization of High%2DDimensional Data Via Dimension Reorderings.



Structural Periodic Measures for Time%2DSeries Data.

Indexing Multidimensional Time%2DSeries.


Rotation invariant indexing of shapes and line drawings.


A MPAA%2DBased Iterative Clustering Algorithm Augmented by Nearest Neighbors Search for Time%2DSeries Data Streams.

A Multi%2Dmetric Index for Euclidean and Periodic Matching.

Fast Burst Correlation of Financial Data.
Abstract. We examine the problem of monitoring and identification of correlated burst patterns in multi-stream time series databases. Our methodology is comprised of two steps: a burst detection part, followed by a burst indexing step. The burst detection scheme imposes a variable threshold on the examined data and takes advantage of the skewed distribution that is typically encountered in many applications. The indexing step utilizes a memory-based interval index for effectively identifying the overlapping burst regions. While the focus of this work is on financial data, the proposed methods and data-structures can find applications for anomaly or novelty detection in telecommunications and network traffic, as well as in medical data. Finally, we manifest the real-time response of our burst indexing technique, and demonstrate the usefulness of the approach for correlating surprising volume trading events at the NY stock exchange. 1
Fast Burst Correlation of Financial Data.
Abstract. We examine the problem of monitoring and identification of correlated burst patterns in multi-stream time series databases. Our methodology is comprised of two steps: a burst detection part, followed by a burst indexing step. The burst detection scheme imposes a variable threshold on the examined data and takes advantage of the skewed distribution that is typically encountered in many applications. The indexing step utilizes a memory-based interval index for effectively identifying the overlapping burst regions. While the focus of this work is on financial data, the proposed methods and data-structures can find applications for anomaly or novelty detection in telecommunications and network traffic, as well as in medical data. Finally, we manifest the real-time response of our burst indexing technique, and demonstrate the usefulness of the approach for correlating surprising volume trading events at the NY stock exchange. 1
On Periodicity Detection and Structural Periodic Similarity.

Indexing Multi%2DDimensional Trajectories for Similarity Queries.

Mining Time Series Data.
The last decade has witnessed a tremendous growths of interests in applications that deal with querying and mining of time series data. Numerous representation methods for dimensionality reduction and similarity measures geared towards time series have been introduced. Each individual work introducing a particular method has made specific claims and, aside from the occasional theoretical justifications, provided quantitative experimental observations. However, for the most part, the comparative aspects of these experiments were too narrowly focused on demonstrating the benefits of the proposed methods over some of the previously introduced ones. In order to provide a comprehensive validation, we conducted an extensive set of time series experiments re-implementing 8 different representation methods and 9 similarity measures and their variants, and testing their effectiveness on 38 time series data sets from a wide variety of application domains. In this paper, we give an overview of these different techniques and present our comparative experimental findings regarding their effectiveness. Our experiments have provided both a unified validation of some of the existing achievements, and in some cases, suggested that certain claims in the literature may be unduly optimistic. 1.
Elastic Translation Invariant Matching of Trajectories.

Iterative Incremental Clustering of Time Series.
We present a novel anytime version of partitional clustering  algorithm, such as k-Means and EM, for time series. The algorithm works by  leveraging off the multi-resolution property of wavelets. The dilemma of  choosing the initial centers is mitigated by initializing the centers at each  approximation level, using the final centers returned by the coarser  representations. In addition to casting the clustering algorithms as anytime  algorithms, this approach has two other very desirable properties. By working at  lower dimensionalities we can efficiently avoid local minima. Therefore, the  quality of the clustering is usually better than the batch algorithm. In addition,  even if the algorithm is run to completion, our approach is much faster than its  batch counterpart. We explain, and empirically demonstrate these surprising and  desirable properties with comprehensive experiments on several publicly  available real data sets. We further demonstrate that our approach can be  generalized to a framework of much broader range of algorithms or data mining  problems.
Online Amnesic Approximation of Streaming Time Series.
The past decade has seen a wealth of research on time series representations, because the manipulation, storage, and indexing of large volumes of raw time series data is impractical. The vast majority of research has concentrated on representations that are calculated in batch mode and represent each value with approximately equal fidelity. However, the increasing deployment of mobile devices and real time sensors has brought home the need for representations that can be incrementally updated, and can approximate the data with fidelity proportional to its age. The latter property allows us to answer queries about the recent past with greater precision, since in many domains recent information is more useful than older information. We call such representations amnesic.
Rotation invariant distance measures for trajectories.
For the discovery of similar patterns in 1D time-series, it is very typical to perform a normalization of the data (for example a transformation so that the data follow a zero mean and unit standard deviation). Such transformations can reveal latent patterns and are very commonly used in datamining applications. However, when dealing with multidimensional time-series, which appear naturally in applications such as video-tracking, motion-capture etc, similar motion patterns can also be expressed at different orientations. It is therefore imperative to provide support for additional transformations, such as rotation. In this work, we transform the positional information of moving data, into a space that is translation, scale and rotation invariant. Our distance measure in the new space is able to detect elastic matches and can be efficiently lower bounded, thus being computationally tractable. The proposed methods are easy to implement, fast to compute and can have many applications for real world problems, in areas such as handwriting recognition and posture estimation in motion-capture data. Finally, we empirically demonstrate the accuracy and the efficiency of the technique, using real and synthetic handwriting data.
Identifying Similarities%2C Periodicities and Bursts for Online Search Queries.
We present several methods for mining knowledge from the query logs of the MSN search engine. Using the query logs, we build a time series for each query word or phrase (e.g., ‘Thanksgiving ’ or ‘Christmas gifts’) where the elements of the time series are the number of times that a query is issued on a day. All of the methods we describe use sequences of this form and can be applied to time series data generally. Our primary goal is the discovery of semantically similar queries and we do so by identifying queries with similar demand patterns. Utilizing the best Fourier coefficients and the energy of the omitted components, we improve upon the state-of-the-art in time-series similarity matching. The extracted sequence features are then organized in an efficient metric tree index structure. We also demonstrate how to efficiently and accurately discover the important periods in a time-series. Finally we propose a simple but effective method for identification of bursts (long or short-term). Using the burst information extracted from a sequence, we are able to efficiently perform ’query-by-burst ’ on the database of timeseries. We conclude the presentation with the description of a tool that uses the described methods, and serves as an interactive exploratory data discovery tool for the MSN query database. 1.
Indexing multi%2Ddimensional time%2Dseries with support for multiple distance measures.
Although most time-series data mining research has concentrated on providing solutions for a single distance function, in this work we motivate the need for a single index structure that can support multiple distance measures. Our specific area of interest is the efficient retrieval and analysis of trajectory similarities. Trajectory datasets are very common in environmental applications, mobility experiments, video surveillance and are especially important for the discovery of certain biological patterns. Our primary similarity measure is based on the Longest Common Subsequence (LCSS) model, that offers enhanced robustness, particularly for noisy data, which are encountered very often in real world applications. However, our index is able to accommodate other distance measures as well, including the ubiquitous Euclidean distance, and the increasingly popular Dynamic Time Warping (DTW). While other researchers have advocated one or other of these similarity measures, a major contribution of our work is the ability to support all these measures without the need to restructure the index. Our framework guarantees no false dismissals and can also be tailored to provide much faster response time at the expense of slightly reduced precision/recall. The experimental results demonstrate that our index can help speed-up the computation of expensive similarity measures such as the LCSS and the DTW.
Efficient Approximation Of Optimization Queries Under Parametric Aggregation Constraints.
We introduce and study a new class of queries that we refer to as OPAC (optimization under parametric aggregation constraints) queries. Such queries aim to identify sets of database tuples that constitute solutions of a large class of optimization problems involving the database tuples. The constraints and the objective function are specified in terms of aggregate functions of relational attributes, and the parameter values identify the constants used in the aggregation constraints. We develop algorithms that preprocess relations and construct indices to efficiently provide answers to OPAC queries. The answers returned by our indices are approximate, not exact, and provide guarantees for their accuracy. Moreover, the indices can be tuned easily to meet desired accuracy levels, providing a graceful tradeoff between answer accuracy and index space. We present the results of a thorough experimental evaluation analyzing the impact of several parameters on the accuracy and performance of our techniques. Our results indicate that our methodology is effective and can be deployed easily, utilizing index structures such as R-trees. 1
Robust Similarity Measures for Mobile Object Trajectories.
We investigate techniques for similarity analysis of spatio-temporal trajectories for mobile objects. Such kind of data may contain a great amount of outliers, which degrades the performance of Euclidean and Time Warping Distance. Therefore, here we propose the use of non-metric distance functions based on the Longest Common Subsequence (LCSS), in conjunction with a sigmoidal matching function. Finally, we compare these new methods to various L p Norms and also to Time Warping distance (for real and synthetic data) and we present experimental results that validate the accuracy and efficiency of our approach, especially under the strong presence of noise.
Discovering Similar Multidimensional Trajectories.
We investigate techniques for analysis and retrieval of object trajectories in a two or three dimensional space. Such kind of data usually contain a great amount of noise, that makes all previously used metrics fail. Therefore, here we formalize non-metric similarity functions based on the Longest Common Subsequence (LCSS), which are very robust to noise and furthermore provide an intuitive notion of similarity between trajectories by giving more weight to the similar portions of the sequences. Stretching of sequences in time is allowed, as well as global translating of the sequences in space. Efficient approximate algorithms that compute these similarity measures are also provided. We compare these new methods to the widely used Euclidean and Time Warping distance functions (for real and synthetic data) and show the superiority of our approach, especially under the strong presence of noise. We prove a weaker version of the triangle inequality and employ it in an indexing structure to answer nearest neighbor queries. Finally, we present experimental results that validate the accuracy and efficiency of our approach. 1
Non%2Dlinear dimensionality reduction techniques for classification and visualization.
In this paper we address the issue of using local embeddings for data visualization in two and three dimensions, and for classification. We advocate their use on the basis that they provide an efficient mapping procedure from the original dimension of the data, to a lower intrinsic dimension. We depict how they can accurately capture the user&#039;s perception of similarity in high-dimensional data for visualization purposes. Moreover, we exploit the low-dimensional mapping provided by these embeddings, to develop new classification techniques, and we show experimentally that the classification accuracy is comparable (albeit using fewer dimensions) to a number of other classification procedures.
